Macchina URM

= La macchina URM =

Table of contents

1 Unlimited Register Machine 1.1 Istruzioni 2 Un semplice programma

Unlimited Register Machine

La URM è una idealizzazione matematica di un computer basata su di una macchina inventata nel 1936 da J. C. Shepherdson e H. E. Sturgis. La URM è una macchina ideale dotata di infiniti registri (un po' come la macchina di Turing) chiamati R₁, R₂, R₃, ..., che contengono un numero naturale. Si denota con r_n il contenuto del registro R_n. Per eseguire delle computazioni la macchina URM deve essere caricata con un programma P e con una configurazione iniziale di numeri naturali nei registri R₁, R₂, R₃, ... . La URM inizia la computazione accedendo all'istruzione I₁, I₂, ... . In base alle istruzioni che legge il contenuto dei registri può venire alterato o meno.

Le istruzioni della URM sono solo quattro, ma con queste è possibile risolvere qualsiasi problema computabile.

Istruzioni

1. Z(n), n=1, 2, 3, ... . In risposta a questa istruzione la URM cambia il valore del registro n a zero, lasciando gli altri registri inalterati: r_n := 0.

2. S(n), n=1, 2, 3, ... . In risposta a questa istruzione la URM aumenta il contenuto del registro n di una unità, lasciando gli altri registri inalterati, r_n := r_n + 1.

3. T(m,n), m,n=1, 2, 3, ... . In risposta a questa istruzione la URM trasferisce il contenuto del registro m nel registro n, tutti gli altri registri compreso R_m rimangono inalterati, r_n := r_m.

4. J(m,n,q); m,n,q=1, 2, 3, ... .In risposta a questa istruzione la URM confronta il contenuto dei registri R_m ed R_n se:

• r_m &ne r_n allora continua con l'istruzione successiva nel programma,
• r_m = r_n allora salta all'istruzione q nel programma.

---

Un semplice programma

Questo programma calcola la somma di due numeri x e y. Perché questo programma funzioni dovrà essere inizializzato con x,y,0,0,...; il programma continuerà a sommare uno ad r₁ usando un altro registro come contatore, in questo caso R₃, per contare quante volte r₁ è stato incrementato. Il programma terminerà quando r₃ = y restituendo il valore 'x + y' in R₁.

I₁ J(3,2,5)
I₂ S(1)
I₃ S(3)
I₄ J(1,1,1)

---

|